/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package Application.MainForm;

import java.util.ArrayList;

/**
 * Az elemek autmatikus elrendezeset eloallito osztaly.
 * @see http://www.graphviz.org/Documentation/TSE93.pdf
 * @author Stikmann
 */
public class GraphLayout {
    /**
     * A graf egy csucsat reprezentalo osztaly, gyakorlatilag struct.
     */
    class GraphNode{
        public int x,y;
        public int osszle;
        public int rank;
        public boolean touched;
        public boolean csakkimenoel;
        public boolean virtual;
    }

    GraphNode nodes[];

    /**
     * A graf egyelet reprezentaloosztaly, gyakorlatilag struct
     */
    class GraphEdge{
        public int honnan, hova;
        public boolean touched;
        public boolean reversed;
        public GraphEdge(int ahonnan, int ahova){
            honnan=ahonnan;
            hova=ahova;
        }

        /**
         * Az el virtualis megforditasa az aciklikussa tevo algoritmushoz.
         */
        public void reverse(){
            int tmp=honnan;
            honnan=hova;
            hova=tmp;
            reversed=!reversed;
        }
    }

    ArrayList<GraphEdge> edges;
    int maxx,maxy;
    int maxrank;

    /**
     * Konstruktor
     * @param num A graf csucsainak szama
     */
    public GraphLayout(int num){
        nodes=new GraphNode[num];
        for(int i=0;i<num;++i)
            nodes[i]=new GraphNode();
        edges=new ArrayList();
        maxx=maxy=0;
    }

    /**
     * Iranyitott El hozzaadasa a grafhoz
     * @param honnan A csucs indexe ahonnan kotunk
     * @param hova A csucs indexe ahonnan kotunk
     */
    public void addEdge(int honnan, int hova){
        if (honnan==hova)
            return;
        for (GraphEdge edge:edges)
            if (edge.honnan==honnan && edge.hova==hova /*||
                edge.honnan==hova && edge.honnan==hova*/)
                return;
        edges.add(new GraphEdge(honnan,hova));
    }

    /**
     * A graf aciklikussa tetele.
     */
    private void acyclize(){
        for (GraphNode node:nodes)
            node.touched=false;
        nodes[0].touched=true;

        while(true){
            boolean volttouch=false;
            for (GraphEdge edge:edges)
                if (!edge.touched && nodes[edge.honnan].touched)
                    if(nodes[edge.hova].touched){
                        edge.reverse();
                        edge.touched=true;
                        volttouch=true;
                    }
                    else
                    {
                        nodes[edge.hova].touched=true;
                        edge.touched=true;
                        volttouch=true;
                    }
            if (!volttouch)
                break;
        }
    }

    /**
     * A csucsok besorolasa, kesobbi x koordinatajuk meghatarozasa.
     */
    private void assignRanks(){
        int rankmost=1;
        for (GraphNode node:nodes){
            node.touched=false;
            node.rank=0;
        }
            
        while(true){
            boolean voltrank=false;

            for (GraphNode node:nodes)
                node.csakkimenoel=true;

            for (GraphEdge edge:edges)
                if (nodes[edge.honnan].rank==0)
                    nodes[edge.hova].csakkimenoel=false;

            for (GraphNode node:nodes)
                if(node.rank==0 && node.csakkimenoel){
                    node.rank=rankmost;
                    voltrank=true;
                }
            ++rankmost;
            if (!voltrank)
                break;
        }

        maxrank=rankmost;
    }

    /**
     * A hosszu, rank-kozi elek minden kozbulso rankban kapnak egy virtualis
     * csucsot, igy lehet megtorni oket rankonkent.
     */
    public void makeVirtualNodes(){
        int pluszkell=0;
        for (GraphEdge edge:edges)
            if(nodes[edge.hova].rank-nodes[edge.honnan].rank>1)
            pluszkell+=nodes[edge.hova].rank-nodes[edge.honnan].rank-1;

        GraphNode tmp[]=new GraphNode[nodes.length+pluszkell];

        for (int i=0;i<nodes.length;++i)
            tmp[i]=nodes[i];

        for (int i=nodes.length;i<tmp.length;++i){
            tmp[i]=new GraphNode();
            tmp[i].virtual=true;
        }

        int pluszthova=nodes.length; /* ide pakoljuk amjd az új node-okat */
        nodes=tmp;
        for (int edgeind=0;edgeind<edges.size();++edgeind){
            GraphEdge edge=edges.get(edgeind);
            int honnanrank=nodes[edge.honnan].rank;
            int hovarank=nodes[edge.hova].rank;
            if(hovarank-honnanrank>1){
                int tmphova=edge.hova;
                edge.hova=pluszthova;
                nodes[pluszthova].rank=honnanrank+1;
                ++pluszthova;
                for(int i=honnanrank+2;i<hovarank;++i){
                    GraphEdge newedge=new GraphEdge(pluszthova-1,pluszthova);
                    newedge.reversed=edge.reversed;
                    edges.add(newedge);
                    nodes[pluszthova].rank=i;
                    ++pluszthova;
                }
                GraphEdge newedge=new GraphEdge(pluszthova-1,tmphova);
                newedge.reversed=edge.reversed;
                edges.add(newedge);
            }
        }
    }

    /**
     * A csucsok kezdeti poziciojanak meghatarozasa
     */
    public void initialPositions(){
        for(int rankmost=1;rankmost<maxrank;++rankmost)
        {
            int y=0;
            for (GraphNode node:nodes)
                if(node.rank==rankmost){
                    node.x=rankmost*120;
                    node.y=y*100;
                    ++y;
                }
        }
    }

    /**
     * A csucsok poziciojanak finomitasa, hogy rovidebb legyen az ossz-el-hossz
     */
    public void refinePositions(){

        for (GraphNode node:nodes)
            node.osszle=1;

        for (GraphEdge edge:edges){
            int tmpy=(nodes[edge.honnan].y/nodes[edge.honnan].osszle+
                      nodes[edge.hova].y/nodes[edge.hova].osszle)/2;
            nodes[edge.honnan].y+=tmpy;
            nodes[edge.hova].y+=tmpy;
            nodes[edge.honnan].osszle+=1;
            nodes[edge.hova].osszle+=1;
        }

        for (GraphNode node:nodes)
            node.y=node.y/node.osszle;

        for(int rankmost=0;rankmost<maxrank;++rankmost)
        {
            /* egyranku node-ok */
            ArrayList<GraphNode> jonodeok=new ArrayList<GraphNode>();
             for (GraphNode node:nodes)
                 if(node.rank==rankmost)
                     jonodeok.add(node);
             
             /* szetcsapunk koztuk */
             while (true){
                boolean voltathelyezes=false;
                for (GraphNode node1:jonodeok)
                for (GraphNode node2:jonodeok){
                    int mennyivel=60;

                    if (node1.virtual)
                         mennyivel-=20;
                    if (node2.virtual)
                         mennyivel-=20;

                    if (node1!=node2 && Math.abs(node1.y-node2.y)<(mennyivel*2-20)){
                         int kozep=(node1.y+node2.y)/2;
                         if (node1.y>node2.y){
                             node1.y=kozep+mennyivel;
                             node2.y=kozep-mennyivel;
                         } else{
                             node1.y=kozep-mennyivel;
                             node2.y=kozep+mennyivel;
                         }
                         voltathelyezes=true;
                    }
                    for (GraphNode node:jonodeok)
                        if (node.y<0){
                            node.y=10;
                             voltathelyezes=true;
                        }
                }

                if(!voltathelyezes)
                        break;
            }
        }

    }

    /**
     * A graf-csucs-elrendezes elkeszitese. Normalisan a krealas es az elek
     * hozzaadasa utan ezt hivja meg a hasznalo fuggveny, majd kiolvassa a
     * nodes mezo tartalmat.
     */
    public void doLayout(){
        while (true){
            assignRanks();
            boolean mrn=false;
            for(GraphNode node:nodes)
                if (node.rank==0)
                    mrn=true;
            
            if (!mrn)
                break;

            /* maradt rank nelkuli node:nem acyclikus a graf. torjuk meg a ciklust es RETRY*/
            for (GraphEdge edge:edges)
            if (nodes[edge.honnan].rank==0 &&
                nodes[edge.hova].rank==0 && Math.random()<0.5){
                edge.reverse();
                break;
            }
            
       }

        makeVirtualNodes();
        initialPositions();
        if (nodes.length<100)
            for(int i=0;i<100;++i)
                refinePositions();

        maxx=maxy=0;
        for(GraphNode node:nodes){
            if(node.x>maxx)
                maxx=node.x;
            if(node.y>maxy)
                maxy=node.y;
        }
        maxx+=100;
        maxy+=100;
    }

}
